#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<vector<int>> ret;
    bool check[10];
    int nums[22]={0};
    vector<int> cur;
    int n;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        n=nums.size();
        dfs(nums);
        return ret;
    }
    void dfs(vector<int>& vec)
    {
        if(cur.size()==n) ret.push_back(cur);
        else
        {
            for(int i=0;i<n;i++)
            {
                if(check[i]==true||(i!=0&&vec[i]==vec[i-1]&&check[i-1]==false)) continue;
                cur.push_back(vec[i]);
                check[i]=true;
                dfs(vec);
                cur.pop_back();
                check[i]=false;
            }
        }
    }
};